package utils;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.Stack;


public class AdjacencyMatrix<T> extends GraphMatrix<T, Integer> 
{
	public AdjacencyMatrix(Collection<T> values) {
		super(values, true);
		
		for(int row = 0; row < this.size; row++)
		{
			for(int col = 0; col < this.size; col++)
			{
				if(row == col)
				{
					this.set(row, col, 1);
				}
				else
				{
					this.set(row, col, 0);
				}
			}
		}
	}
	
	public AdjacencyMatrix() {
		super(true);
	}
	
	@Override
	public void addRowAndCol(ArrayList<T> values)
	{
		int oldSize = this.size;
		
		super.addRowAndCol(values);
		
		for(int row = oldSize; row < this.size; row++)
		{
			for(int col = oldSize; col < this.size; col++)
			{
				this.matrix.get(row).set(col, 1);
			}
		}
	}
	
	public ArrayList<T> getNeighbours(T value)
	{
		ArrayList<T> row = new ArrayList<T>();
		
		int rowIndex = this.getIndex(value);
		
		for(int i = 0; i < this.size; i++)
		{
			if(this.get(rowIndex, i) > 0)
			{
				row.add(this.keys.get(i));
			}
		}

		return row;
	}
	
	public void increase(T row, T col)
	{
		int currentValue = this.get(row, col);
		this.set(row, col, currentValue + 1);
	}
	
	public void decrease(T row, T col)
	{
		int currentValue = this.get(row, col);
		this.set(row, col, currentValue - 1);
	}
	

	private Stack<T> findPath(T begin, Stack<T> currentPath, ArrayList<T> falseValues, boolean shuffled)
	{
		ArrayList<T> neighbours = this.getNeighbours(begin);
		if(shuffled)
		{
			Collections.shuffle(neighbours);
		}
		
		if(!currentPath.contains(begin) && neighbours.contains(currentPath.peek()))
		{
			currentPath.add(begin);
			return currentPath;
		}
		
		neighbours.removeAll(falseValues);
		
		falseValues.add(begin);
		
		for(Iterator<T> it = neighbours.iterator(); it.hasNext();)
		{
			T node = it.next();

			Stack<T> newPath = this.findPath(node, (Stack<T>) currentPath.clone(), falseValues, shuffled);
			if(newPath.size() > 1) 
			{	
				currentPath = newPath;
				currentPath.add(node);
				break;
			}
			else
			{
				falseValues.add(node);
			}
		}
		return currentPath;
	}
	
	public Stack<T> findPath(T begin, T end)
	{
		Stack<T> stack = new Stack<T>();
		stack.push(end);
		ArrayList<T> falseRoom = new ArrayList<T>();
		Stack<T> result = this.findPath(begin, stack, falseRoom, false);
		result.add(begin);
		
		Collections.reverse(result);

		return result;
	}
}
